//
//  Problem647.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/2.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 647. 回文子串
 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

 示例 1：
     输入："abc"
     输出：3
     解释：三个回文子串: "a", "b", "c"
 示例 2：
     输入："aaa"
     输出：6
     解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
 提示：
    输入的字符串长度不会超过 1000 。
 */
@objcMembers class Problem647: NSObject {
    func solution() {
        print(countSubstringsMidChars("abc"))
    }
    
    /*
     动态规划 超时
     1: 创建一个二位数组dp[len][len]
     2: dp[i][j]: i~j是否是回文 = dp[i+1][j-1] == 1 ? s[i] == s[j] : 0
     3: 求和
     */
    func countSubstrings(_ s: String) -> Int {
        if s.count <= 1 {
            return s.count
        }
        
        let chars = Array(s)
        var dp = Array(repeating: Array(repeating: -1, count: s.count), count: s.count)
        for i in 0..<s.count {
            dp[i][i] = 1
        }
        
        var value = 0
        for i in 0..<s.count {
            for j in i..<s.count {
                if dp[i][j] == -1 {
                    value += getSubStringsDP(chars, &dp, i, j)
                } else {
                    value += dp[i][j]
                }
            }
        }
        
        return value
    }
    
    func getSubStringsDP(_ chars: [Character], _ dp: inout [[Int]], _ i: Int, _ j: Int) -> Int {
        if i > j {
            return 0
        }
        if dp[i][j] != -1 {
            return dp[i][j]
        }
        
        if i == j - 1 {
            dp[i][j] = chars[i] == chars[j] ? 1 : 0
        } else {
            let next = getSubStringsDP(chars, &dp, i+1, j-1)
            if next == 0 {
                dp[i][j] = 0
            } else {
                dp[i][j] = chars[i] == chars[j] ? 1 : 0
            }
        }
        return dp[i][j]
    }
    
    func countSubstringsMidChars(_ s: String) -> Int {
        let n = s.count
        var ans = 0
        let chars = Array(s)
        for i in 0 ..< 2 * n - 1 {
            var l = Int(i / 2)
            var r = Int(i / 2) + Int(i % 2)

            while (l >= 0 && r < n && chars[l] == chars[r]) {
                l -= 1
                r += 1
                ans += 1
                
            }
        }
             
        return ans;
    }
    
    func countSubstringsMid(_ s: String) -> Int {
        let n = s.count
        var ans = 0
        for i in 0 ..< 2 * n - 1 {
            var l = Int(i / 2)
            var r = Int(i / 2) + Int(i % 2)
            print(l, r)
            
            
            while (l >= 0 && r < n) {
                if s[s.index(s.startIndex, offsetBy: l)] != s[s.index(s.startIndex, offsetBy: r)] {
                    break
                }
                l -= 1
                r += 1
                ans += 1
                
            }
            print(ans)
        }
             
        return ans;
    }
}
